Chihik's Blog

An Ac a day, keeps the doctor away!

CF113D Museum

发布于 2020-11-27 | 分类于 高斯消元 、 概率dp | 5分钟 | 691字数

fi,jf_{i,j}：两人分别在房间 i,ji,j 的概率。初始状态 fa,b=1f_{a,b}=1

fi,j=pipjfi,j+∑(i,u)∈E∑(j,v)∈E1−pudeg⁡u1−pvdeg⁡vfu,vf_{i,j}=p_ip_jf_{i,j}+\sum_{(i,u) \in E}\sum_{(j,v) \in E} \frac{1-p_u}{\deg_u} \frac{1-p_v}{\deg_v}f_{u,v}

阅读全文 »

P3211 [HNOI2011]XOR和路径

发布于 2020-11-27 | 分类于 高斯消元 、 概率dp | 4分钟 | 606字数

异或的期望不能直接算，对每一位单独考虑。

f[u][0/1]f[u][0/1]:节点 uu 的第 ii 位为 0/10/1 的概率。

注意经过节点 uu 的概率不一定为 11 ，所以 f[u][0]+f[u][1]f[u][0]+f[u][1] 的值不一定为 11。

阅读全文 »

CF575A Fibonotci

发布于 2020-11-25 | 分类于 矩阵乘法 、 线段树 | 1分钟 | 164字数

考试的时候写了3.5h , 考后又写了2h 才过掉。

每次修改只会影响两个矩阵，可以暴力计算。

我们知道矩阵乘法有结合律，那么两次修改之间的矩阵可以快速求出乘积。

阅读全文 »

P5437 【XR-2】约定

发布于 2020-11-25 | 分类于 拉格朗日插值 | 6分钟 | 889字数

每一条边被选中的概率： n−1n(n−1)2=2n\frac{n-1}{\frac{n(n-1)}{2}}=\frac{2}{n}

所以答案为：

2n∑i=1n−1∑j=i+1n(i+j)k\frac{2}{n} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (i+j)^k

阅读全文 »

P5929 [POI1999]地图

发布于 2020-11-25 | 分类于 dp | 3分钟 | 480字数

至少有一半不小于 A(k)A(k) , 至少有一半不大于 A(k)A(k)

所以 A(k)A(k) 应该是选出的区域人口的中位数。

为了使误差尽可能小，每次应该取排序后连续的一段区间染相同颜色。

阅读全文 »

SP4060 KPGAME - A game with probability

发布于 2020-11-25 | 分类于 博弈论 、 概率dp | 5分钟 | 720字数

dp[0/1][i]dp[0/1][i] :有 ii 颗石子 Alice/Bob 为先手，Alice 赢的概率

令 PP 为 Alice 拿走石子的概率， QQ 为 Bob 拿走石子的概率。

{dp[0][i]=dp[1][i−1]∗P+dp[1][i]∗(1−P)dp[1][i]=dp[0][i−1]∗Q+dp[0][i]∗(1−Q)\begin{cases}

阅读全文 »

P1560 [USACO5.2]蜗牛的旅行

发布于 2020-10-14 | 分类于 搜索 | 3分钟 | 465字数

这道题是一道典型的搜索题，我们用dfs(x,y,step,s)dfs(x,y,step,s)表示蜗牛在(x,y)(x,y)这个点，走了stepstep步，当前的方向（起点的s=0s=0，特殊处理一下）。

当蜗牛确定一个方向后，我们就不断让它前进，同时记录它走过的格子，直到它遇到障碍，出界或者到达已走过的点停止。

如果蜗牛遇到障碍，我们就枚举每个方向，因为前方有障碍，后方已经走过，所以蜗牛只会向左或向右转，不需要特殊处理。

阅读全文 »
0%